#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
void shellsort(int* a,int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int j = 0; j < gap; j++)
		{
			for (int i = j; i < n - gap; i += gap)
			{
				int end = i;
				int k = a[end + gap];
				while (end >= 0)
				{
					if (k > a[end])
					{
						a[end + gap] = a[end];
						end-=gap;
					}
					else
					{
						break;
					}

				}
				a[end + gap] = k;
			}
		}
	}	
}

void shellsort2(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int k = a[end + gap];
			while (end >= 0)
			{
				if (k > a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = k;
		}
	}
}
void swao(int* a, int* b)
{
	int c = *a;
	*a = *b;
	*b = c;
}
void quicksort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int ki = left;
	int begin = left;
	int end = right;
	while (begin < end)
	{
		while (begin < end&&a[end]<a[ki])
		{
			end--;
		}
		while (begin<end && a[begin]>a[ki])
		{
			begin++;
		}
		swao(&a[end], &a[begin]);
	}
	swao(&a[ki], &a[begin]);
	quicksort(a, left, begin - 1);
	quicksort(a, begin+1, right);
}
int main()
{
	int a[] = { 4331,43124,211,3214,435,437,52456,652,2575274,52,321,141,1 };
	int len = sizeof(a) / sizeof(int);
	for (int i = 0; i < len; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
	quicksort(a, 0,len-1);
	for (int i = 0; i < len; i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
}